GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Greedy-Algorithmus</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Greedy-Algorithmus</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p><b>Greedy-Algorithmen</b> oder <b>gierige Algorithmen</b> bilden eine spezielle Klasse von <a href="Algorithmus" title="Algorithmus">Algorithmen</a> in der <a href="Informatik" title="Informatik">Informatik</a>. Sie zeichnen sich dadurch aus, dass sie schrittweise den Folgezustand auswählen, der zum Zeitpunkt der Wahl den größten Gewinn bzw. das beste Ergebnis (berechnet durch eine <a href="Optimierungsproblem" title="Optimierungsproblem">Bewertungsfunktion</a>) verspricht (z. B. <a href="Gradientenverfahren" title="Gradientenverfahren">Gradientenverfahren</a>).

</p><p>Greedy-Algorithmen sind oft schnell, lösen viele Probleme aber nicht optimal.

</p>

<div class="mw-heading mw-heading2"><h2 id="Anschauliches_Beispiel">Anschauliches Beispiel</h2></div>

<p>Ein Wanderer möchte möglichst hoch hinaus. Es ist jedoch so neblig, dass er nur 5 Meter weit sehen kann. Er verfolgt eine einfache Strategie: Er sieht sich in seiner Umgebung um, welcher Punkt der höchste ist und geht dann dorthin. Dort schaut er sich wieder um, welcher Punkt der höchste ist, geht dorthin, und so weiter, bis er keinen höheren Punkt mehr findet.

</p><p>Dieses Beispiel zeigt die typischen Eigenschaften eines Greedy-Algorithmus:

</p>

<ul><li>Um das große Ziel zu erreichen, sind kleine Einzelschritte nötig. Der Wanderer geht in jedem Schritt maximal 5 Meter weit.</li>

<li>In jedem der Einzelschritte sind nur begrenzt Informationen verfügbar. Der Wanderer sieht jeweils nur die umliegenden 5 Meter.</li>

<li>Nachdem ein Einzelschritt ausgeführt wurde, wird dieser Schritt nicht mehr zurückgenommen. Der Wanderer denkt nicht darüber nach, 3 Schritte zurückzugehen, um an einem anderen Ort einen besseren Weg zu finden.</li>

<li>Die gefundene Lösung ist nicht notwendigerweise die global optimale. Der Wanderer erreicht wahrscheinlich den Gipfel eines kleinen Hügels statt den eines großen Berges.</li>

<li>Je nach Ausgangssituation kann sich die gefundene Lösung stark unterscheiden.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Optimierungsprobleme_auf_Unabhängigkeitssystemen"><span id="Optimierungsprobleme_auf_Unabh.C3.A4ngigkeitssystemen"></span>Optimierungsprobleme auf Unabhängigkeitssystemen</h2></div>

<p>Ein Greedy-Algorithmus findet für ein <a href="Optimierungsproblem" title="Optimierungsproblem">Optimierungsproblem</a> auf <a href="Unabh%C3%A4ngigkeitssystem" title="Unabhängigkeitssystem">Unabhängigkeitssystemen</a> genau dann die optimale Lösung für alle Bewertungsfunktionen, wenn die zulässigen Lösungen die unabhängigen Mengen eines <a href="Matroid" title="Matroid">Matroids</a> sind. Sonst führt der Algorithmus lediglich zu einem <a href="Extremwert" title="Extremwert">lokalen Optimum</a>. Beispiele dafür sind das <a href="Rucksackproblem" title="Rucksackproblem">Rucksackproblem</a> und das <a href="Problem_des_Handlungsreisenden" title="Problem des Handlungsreisenden">Problem des Handlungsreisenden</a>. Bei diesen Problemen ist es wesentlich aufwändiger, die optimale Lösung zu finden, da die Probleme <a href="NP-Vollst%C3%A4ndigkeit" title="NP-Vollständigkeit">NP-vollständig</a> sind.

</p>

<div class="mw-heading mw-heading3"><h3 id="Algorithmus_für_das_Maximierungsproblem"><span id="Algorithmus_f.C3.BCr_das_Maximierungsproblem"></span>Algorithmus für das Maximierungsproblem</h3></div>

<p>Zu einem <a href="Matroid" title="Matroid">Matroid</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (E,U)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (E,U)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/356d7c9c28b2715d96a33cec37cf992a79a51899.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.401ex; height:2.843ex;" alt="{\displaystyle (E,U)}" loading="lazy"></span> sei eine Gewichtsfunktion <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w\colon E\rightarrow \mathbb {R} ^{+}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w\colon E\rightarrow \mathbb {R} ^{+}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74ea167d1be229e6c404e39ab0838b313887b70e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.277ex; height:2.509ex;" alt="{\displaystyle w\colon E\rightarrow \mathbb {R} ^{+}}" loading="lazy"></span> gegeben. Der folgende Algorithmus findet eine schwerste unabhängige Menge, bestimmt also ein <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F\in U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F\in U}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6d8eef3afea13ea52cc89ae2aa760e8b81d3e3af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.364ex; height:2.176ex;" alt="{\displaystyle F\in U}" loading="lazy"></span>, das <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w(F):=\sum _{e\in F}w(e)}">

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w(F):=\sum _{e\in F}w(e)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/850e00b6816cb7b69b1e33632e7ff782f7b08f3c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:17.259ex; height:5.676ex;" alt="{\displaystyle w(F):=\sum _{e\in F}w(e)}" loading="lazy"></span> maximiert:

</p>

<pre> 1 // Ordne alle Elemente in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"></span> nach absteigendem Gewicht

2 <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w(e_{1})\geq \ldots \geq w(e_{n})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w(e_{1})\geq \ldots \geq w(e_{n})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5769d378e842314194f9c5df473c8370e30bae1c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.307ex; height:2.843ex;" alt="{\displaystyle w(e_{1})\geq \ldots \geq w(e_{n})}" loading="lazy"></span>

3

4 <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T=\varnothing }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T=\varnothing }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7f104a151502595d790131c947899ab4cd8d8894.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.543ex; height:2.176ex;" alt="{\displaystyle T=\varnothing }" loading="lazy"></span>;

5

6 for (k = 1; k <= n; k++) {

7 if <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (T\cup \{e_{k}\}\in U)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (T\cup \{e_{k}\}\in U)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1be98a1879922f7ce405302abe91c044a7b6f740.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.149ex; height:2.843ex;" alt="{\displaystyle (T\cup \{e_{k}\}\in U)}" loading="lazy"></span>

8 <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T=T\cup \{e_{k}\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T=T\cup \{e_{k}\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e101b80bd1251d11d8a388c3c1c922d354d31835.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.451ex; height:2.843ex;" alt="{\displaystyle T=T\cup \{e_{k}\}}" loading="lazy"></span>

9 }

10

11 Ausgabe der Lösung <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"></span>

</pre>

<div class="mw-heading mw-heading4"><h4 id="Verallgemeinerbarkeit">Verallgemeinerbarkeit</h4></div>

<p>Der Algorithmus löst auch Maximierungs- und Minimierungsprobleme zu <i>beliebigen</i> Gewichtsfunktionen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w\colon E\to \mathbb {R} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w\colon E\to \mathbb {R} }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4f188fbfad36a55ee50297e4bc75feb1cac489f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.766ex; height:2.176ex;" alt="{\displaystyle w\colon E\to \mathbb {R} }" loading="lazy"></span>: In einer Lösung für das Maximierungsproblem treten negative Gewichte nicht auf, Elemente mit negativem Gewicht können also vom Algorithmus ignoriert werden. Die Lösung des Problems, eine minimale unabhängige Menge zu finden, kann auf die Lösung des Maximierungsproblems zurückgeführt werden, indem man die Gewichte durch ihre additiven Inversen ersetzt.

</p>

<div class="mw-heading mw-heading4"><h4 id="Laufzeit">Laufzeit</h4></div>

<p>Ist <i>L</i> die Laufzeit der Prüfung einer Menge auf Unabhängigkeit, so ist die Laufzeit des Algorithmus durch <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(|E|\cdot (\log(|E|+L)))}">

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(|E|\cdot (\log(|E|+L)))}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9d09eb6ce1a745e73dd1e11334492687c6c2d476.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.491ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(|E|\cdot (\log(|E|+L)))}" loading="lazy"></span> gegeben. Im besten Fall wird sie also durch das <a href="Sortierverfahren" title="Sortierverfahren">Sortierverfahren</a> dominiert. Wenn die Unabhängigkeitsprüfung dagegen <a href="NP-vollst%C3%A4ndig" class="mw-redirect" title="NP-vollständig">NP-vollständig</a> ist, ist der Algorithmus praktisch nutzlos.

</p>

<div class="mw-heading mw-heading3"><h3 id="Algorithmus_für_das_Minimierungsproblem"><span id="Algorithmus_f.C3.BCr_das_Minimierungsproblem"></span>Algorithmus für das Minimierungsproblem</h3></div>

<p>Zu einem <a href="Matroid" title="Matroid">Matroid</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (E,U)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (E,U)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/356d7c9c28b2715d96a33cec37cf992a79a51899.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.401ex; height:2.843ex;" alt="{\displaystyle (E,U)}" loading="lazy"></span> sei eine Gewichtsfunktion <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w\colon E\rightarrow \mathbb {R} ^{+}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w\colon E\rightarrow \mathbb {R} ^{+}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74ea167d1be229e6c404e39ab0838b313887b70e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.277ex; height:2.509ex;" alt="{\displaystyle w\colon E\rightarrow \mathbb {R} ^{+}}" loading="lazy"></span> gegeben. Der folgende Algorithmus findet eine leichteste Basis, bestimmt also unter den kardinalitätsmaximalen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B\in U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B\in U}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0cc156564e887a76e28c7a8d9d83bafdd058ed96.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.387ex; height:2.176ex;" alt="{\displaystyle B\in U}" loading="lazy"></span> eines, das <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c(B):=\sum _{e\in B}c(e)}">

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(B):=\sum _{e\in B}c(e)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1a535a241fe7405191d40e824c4ad422b5cfe1b3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:15.967ex; height:5.676ex;" alt="{\displaystyle c(B):=\sum _{e\in B}c(e)}" loading="lazy"></span> minimiert:

</p>

<ul><li><a href="Sortierverfahren" title="Sortierverfahren">Sortiere</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"></span>, so dass <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E=\{e_{1},\ldots ,e_{n}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E=\{e_{1},\ldots ,e_{n}\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ac86411a3635b787e3bc23e0b56fec7c7f1d9da5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.817ex; height:2.843ex;" alt="{\displaystyle E=\{e_{1},\ldots ,e_{n}\}}" loading="lazy"></span> mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w(e_{1})\geq w(e_{2})\geq \cdots \geq w(e_{n})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w(e_{1})\geq w(e_{2})\geq \cdots \geq w(e_{n})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a841b23e2ece1cf0dd5efbf75eab040c4c3ae138.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.016ex; height:2.843ex;" alt="{\displaystyle w(e_{1})\geq w(e_{2})\geq \cdots \geq w(e_{n})}" loading="lazy"></span></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T:=E}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/94d1e50b5df3ea4620f2b42c4782d0ee5fd90deb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.157ex; height:2.176ex;" alt="{\displaystyle T:=E}" loading="lazy"></span></li>

<li>Für jedes <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span> von 1 bis <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span>:</li></ul>

<dl><dd><dl><dd>Enthält <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\setminus e_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T\setminus e_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/80e104ca699a07c18563ba600c70d935d0f0f97d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.714ex; height:2.843ex;" alt="{\displaystyle T\setminus e_{i}}" loading="lazy"></span> eine Basis, so setze <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T:=T\setminus e_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T:=T\setminus e_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bad6f3f6b6083258c51d5c81d53326222a5ed442.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.096ex; height:2.843ex;" alt="{\displaystyle T:=T\setminus e_{i}}" loading="lazy"></span>.</dd></dl></dd></dl>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"></span> aus.</li></ul>

<div class="mw-heading mw-heading4"><h4 id="Vergleich_zum_Maximierungsproblem,_Verallgemeinerbarkeit"><span id="Vergleich_zum_Maximierungsproblem.2C_Verallgemeinerbarkeit"></span>Vergleich zum Maximierungsproblem, Verallgemeinerbarkeit</h4></div>

<p>Da positive Gewichte vergeben sind, ist das Problem, nach einer leichtesten Basis-Obermenge zu suchen, äquivalent. <i>Dieses</i> Problem ist dual zum Maximierungsproblem und kann analog auf beliebige Gewichtsfunktionen und das entsprechende Minimierungsproblem verallgemeinert werden.

</p>

<div class="mw-heading mw-heading4"><h4 id="Laufzeit_2">Laufzeit</h4></div>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"></span> die Laufzeit der Prüfung, ob eine Teilmenge von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"></span> Obermenge einer Basis ist, so ist die Laufzeit des Algorithmus durch <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(|E|\cdot (\log(|E|+L)))}">

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(|E|\cdot (\log(|E|+L)))}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9d09eb6ce1a745e73dd1e11334492687c6c2d476.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.491ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(|E|\cdot (\log(|E|+L)))}" loading="lazy"></span> gegeben. Im besten Fall wird sie also durch das <a href="Sortierverfahren" title="Sortierverfahren">Sortierverfahren</a> dominiert. Wenn die Basis-Obermengen-Prüfung dagegen <a href="NP-vollst%C3%A4ndig" class="mw-redirect" title="NP-vollständig">NP-vollständig</a> ist, ist der Algorithmus praktisch nutzlos.

</p>

<div class="mw-heading mw-heading4"><h4 id="Beispiele">Beispiele</h4></div>

<ul><li>Algorithmen von <a href="Algorithmus_von_Kruskal" title="Algorithmus von Kruskal">Kruskal</a> und <a href="Algorithmus_von_Prim" title="Algorithmus von Prim">Prim</a> für die Suche nach einem <a href="Minimaler_Spannbaum" class="mw-redirect" title="Minimaler Spannbaum">minimalen Spannbaum</a></li>

<li>Algorithmus von <a href="Algorithmus_von_Dijkstra" class="mw-redirect" title="Algorithmus von Dijkstra">Dijkstra</a> zur Suche eines kürzesten Weges</li>

<li>Algorithmus von <a href="Huffman-Kodierung" title="Huffman-Kodierung">Huffman</a> zur Bestimmung eines optimalen <a href="Pr%C3%A4fixcode" title="Präfixcode">präfixfreien Codes</a></li>

<li>Algorithmus der <a href="Sukzessive_Einbeziehung" title="Sukzessive Einbeziehung">sukzessiven Einbeziehung</a> zum heuristischen Lösen von <a href="Kombinatorische_Optimierung" title="Kombinatorische Optimierung">kombinatorischen Optimierungsproblemen</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Thomas H. Cormen, Charles Leiserson, <a href="Ronald_L._Rivest" title="Ronald L. Rivest">Ronald L. Rivest</a>, Clifford Stein: <i>Introduction to Algorithms.</i> 2. Auflage. MIT Press, 2001, ISBN 0-262-53196-8.</li>

<li><a href="Bernhard_Korte" title="Bernhard Korte">Bernhard Korte</a>, <a href="Jens_Vygen" title="Jens Vygen">Jens Vygen</a>: <i>Combinatorial Optimization.</i> 3. Auflage. Springer, 2005, ISBN 3-540-25684-9.</li>

<li>James Oxley: <i>Matroid Theory</i>. Oxford Mathematics 1992. ISBN 0-19-853563-5.</li>

<li>Christos H. Papadimitriou und Kenneth Steiglitz: <i>Combinatorial Optimization</i>. Algorithms and Complexity. Prentice Hall Inc. 1982. ISBN 0-13-152462-3.</li>

<li>Jon Lee: <i>A First Course in Combinatorial Optimization</i>. Cambridge Texts in Applied Mathematics 2004. ISBN 0521010128.</li>

<li>Sven Oliver Krumke und Hartmut Noltemeier: <i>Graphentheoretische Konzepte und Algorithmen</i>. 2. Auflage Vieweg-Teubner 2009. ISBN 978-3-8348-0629-1.</li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2023-12-11" href="https://de.wikipedia.org/wiki/?title=Greedy-Algorithmus&oldid=240097417">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>